package dfs;

import java.util.HashSet;
import java.util.Set;

/**
 * MinimumGeneticMutation 最小基因变化
 *
 * @author <a href="zhaoyingling12@163.com">Zhao Simon</a>
 * @description: https://leetcode-cn.com/problems/minimum-genetic-mutation/
 * @date 2021/6/7
 **/
public class MinimumGeneticMutation {
    public static void main(String[] args) {
        String start = "AACCGGTT", end = "AAACGGTA";
        String[] bank = {"AACCGGTA", "AACCGCTA", "AAACGGTA"};
        Solution solution1 = new Solution();
        int min = solution1.minMutation(start, end, bank);
        System.out.println(min);
    }

    static class Solution {

        private int min = Integer.MAX_VALUE;

        public int minMutation(String start, String end, String[] bank) {
            Set<String> visited = new HashSet<>();
            visited.add(start);
            dfs(start, end, bank, visited, 0);
            return min == Integer.MAX_VALUE ? -1 : min;
        }

        private void dfs(String startGene, String endGene, String[] bank, Set<String> visited, int level) {
            if (level >= min) return;
            if (startGene.equals(endGene)) {
                min = Math.min(min, level);
                return;
            }
            for (String gene : bank) {
                if (isLegalChange(startGene, gene) && !visited.contains(gene)) {
                    visited.add(gene);
                    dfs(gene, endGene, bank, visited, level + 1);
                    visited.remove(gene);
                }
            }
        }

        private boolean isLegalChange(String str1, String str2) {
            int diff = 0;
            for (int i = 0; i < str1.length(); i++) {
                if (str1.charAt(i) != str2.charAt(i)) {
                    diff++;
                }
                if (diff > 1) return false;
            }
            return diff == 1;
        }
    }
}
